DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2023.35

Voronoi Diagrams in the Hilbert Metric

Authors: Auguste H. Gezalyan and David M. Mount

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract

The Hilbert metric is a distance function defined for points lying within a convex body. It generalizes the Cayley-Klein model of hyperbolic geometry to any convex set, and it has numerous applications in the analysis and processing of convex bodies. In this paper, we study the geometric and combinatorial properties of the Voronoi diagram of a set of point sites under the Hilbert metric. Given any m-sided convex polygon Ω in the plane, we present two randomized incremental algorithms and one deterministic algorithm. The first randomized algorithm and the deterministic algorithm compute the Voronoi diagram of a set of n point sites. The second randomized algorithm extends this to compute the Voronoi diagram of the set of n sites, each of which may be a point or a line segment. Our algorithms all run in expected time O(m n log n). The algorithms use O(m n) storage, which matches the worst-case combinatorial complexity of the Voronoi diagram in the Hilbert metric.

Cite as

Auguste H. Gezalyan and David M. Mount. Voronoi Diagrams in the Hilbert Metric. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gezalyan_et_al:LIPIcs.SoCG.2023.35,
  author =	{Gezalyan, Auguste H. and Mount, David M.},
  title =	{{Voronoi Diagrams in the Hilbert Metric}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.35},
  URN =		{urn:nbn:de:0030-drops-178851},
  doi =		{10.4230/LIPIcs.SoCG.2023.35},
  annote =	{Keywords: Voronoi diagrams, Hilbert metric, convexity, randomized algorithms}
}

Search Results

Documents authored by Gezalyan, Auguste H.

Voronoi Diagrams in the Hilbert Metric

Abstract

Cite as

Thanks for your feedback!

Could not send message